#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;

class Solution
{
public:
    void remove(string s, const vector<char> &parameter, int m, int n, vector<string> &res)
    {
        int stack = 0, i = m;
        for (; i < s.size(); i++)
        {
            if (s[i] == parameter[0])
                stack++;
            else if (s[i] == parameter[1])
                stack--;
            if (stack >= 0)
                continue;
            for (int j = n; j <= i; j++)
            {
                if (s[j] == parameter[1] && (j == n || s[j - 1] != parameter[1]))
                {
                    auto ss = s.substr(0, j) + s.substr(j + 1);
                    remove(move(ss), parameter, i, j, res);
                }
            }
            return;
        }
        reverse(s.begin(), s.end());
        if (parameter[0] == '(')
        {
            remove(move(s), {parameter[1], parameter[0]}, 0, 0, res);
        }
        else
        {
            res.push_back(move(s));
        }
    }
    vector<string> removeInvalidParentheses(string s)
    {
        vector<string> res;
        remove(move(s), {'(', ')'}, 0, 0, res);
        return res;
    }
};